Міністерство освіти і науки, молоді та спорту України Національний університет „Львівська політехніка” Кафедра СКС Звіт про виконання лабораторної роботи №1 "Дискретна математика"  Львів - 2015 Тема: Множини. Операції над множинами. Алгебраїчні операції. Групи. Мета: Розробити програмне забезпечення, яке перевіряє властивості відображення (ін’єктивність) Теоретична частина: 1.1. Множини Множини є основними об’єктами вивчення у дискретній математиці. Множина - це невпорядкована сукупність об’єктів, які називають елементами множини. Елементами можна вважати довільні об’єкти, які можуть бути названі або означені за допомогою правила, що задає належність до множини. Як правило, множини позначають великими буквами. Прикладе множин: множина всіх трамвайних зупинок міста Львова; множина символів клавіатури ЕОМ; множина зарезервованих слів мови Паскаль; А = {х ǀ х - ціле число і 7 < х < 13}; N = {1, 2, 5, 9, 14, 13} - множина задана перечисленням її елементів. Для будь-якого елемента можна встановити, чи належить він множині
. Запис
означає приналежність елемента
до множини
, а символ «
» - це знак приналежності деякого елемента до множини
. Запис
означає, що елемент
не належить до множини
. 1.2. Операції над множинами Об’єднанням множин
і
(позначається
) називається множина
. Перетином множин
і
(позначається
) називається множина
. Різницею множин
і
(позначається
) називається множина
. Симетрична різниця множин
і
(позначається
) задається як
Порожня множина (позначається Ø) - це множина, яка володіє властивістю
для будь-якого
. Означення 1. Множина
є підмножиною множини
) тоді і тільки тоді, якщо для будь-якого
випливає, що
. Означення 2. Відношення
називається: рефлексивним, якщо
для всіх
; симетричним, якщо з
випливає
для всіх; антисиметричним, якщо з
і
випливає, що
для всіх
; транзитивним, якщо з
і
випливає
для всіх
. Означення 3. Рефлексивне, симетричне і транзитивне відношення
на множині
називається відношенням еквівалентності. Рефлексивне, антисиметричне і транзитивне відношення
на множині
називається відношенням часткового порядку. Означення 4.
тоді і тільки тоді, коли
;
для
тоді і тільки тоді, коли існує
таке, що
і
для
. Як для заданого на деякій множині відношення
можна визначити відношення
таке, що
володіє додатковими властивостями, зокрема - транзитивністю? Таким буде відношення
тоді і тільки тоді і якщо знайдеться таке
, що
для
, які належать даній множині. Відношення
називається транзитивним замиканням відношення
на множині
. Для транзитивного замикання Має місце теорема: Теорема 1. Транзитивне замикання
деякого відношення
є відношення транзитивне. Якщо
- будь-яке транзитивне відношення, таке, що
, тоді
і тобто
- найменше транзитивне відношення, яке включає
. Для знаходження матриці транзитивного замикання відношення
на множині
зі скінченою кількістю елементів можна скористуватись теоремою: Теорема 2. Нехай
- матриця, що задає відношення
на множині
, яка містить
елементів. Тоді матриця
задає транзитивне замикання відношення
. 1.1. Об’єднання А і В – множина, що складається з усіх елементів множини А, всіх елементів множини В і не містить ніяких інших елементів (рис. 1), тобто А ( В = {x | x ( А або x ( В}.
Рис. 1 1.2. Перетин А і В – множина, що складається з тих і тільки з тих елементів, які належать одночасно множині А та множині В (рис. 2), тобто А ( В = {x | x ( А і x ( В}.
Рис. 2 1.3. Різниця А і В (відносне доповнення) – множина, що складається з тих і тільки тих елементів, які належать множині А й не належать множині В (рис. 3), тобто А \ В = {x | x ( А і x ( В}.
Рис. 3 1.4. Диз’юнктивна сума А і В (симетрична різниця) – множина, що складається усіх е...